public class heapSort {
    static void heapify(int[] arr, int len, int i) {
        int largest = i;
        int lSon = largest * 2 + 1;
        int rSon = largest * 2 + 2;
        if (lSon < len && arr[lSon] > arr[largest]) {
            largest = lSon;
        }
        if (rSon < len && arr[rSon] > arr[largest]) {
            largest = rSon;
        }
        if (largest != i) {
            swap(arr, largest, i);
            heapify(arr, len, largest);
        }
    }


    static void heap_sort(int[] arr, int len) {
//        建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, len, i);
        }
//        排序
        for (int i = len - 1; i >= 0; i--) {
            swap(arr, i, 0);
            heapify(arr, i, 0);
        }
    }
    static void swap(int[] arr, int i1, int i2) {
        int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {2, 1, 2, 5, 7, 2, 4, 3, 7, 2, 1, 6, 9, 4, 3, 1, 721, 6, 8, 2, 2, 7};
        heap_sort(arr, arr.length);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
